package william.tree;


/**
 * @author ZhangShenao
 * @date 2024/1/16
 * @description <a href="https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/">...</a>
 */
public class Leetcode104_二叉树的最大深度 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 递归实现
     * 当前树的最大深度=Max(左子树深度,右子树深度)+1
     * <p>
     * 时间复杂度O(N) 对树遍历一次
     * 空间复杂度O(logN) 递归栈深度=二叉树高度
     */
    public int maxDepth(TreeNode root) {
        //递归终止条件
        if (root == null) {
            return 0;
        }

        //递归调用
        //当前树的最大深度=Max(左子树深度,右子树深度)+1
        return (Math.max(maxDepth(root.left), maxDepth(root.right)) + 1);
    }

    /**
     * 迭代实现
     * 采用层序遍历法,通过一个变量记录当前深度。每遍历到新的一层,深度+1
     */
//    public int maxDepth(TreeNode root) {
//        //边界条件校验
//        if (root == null) {
//            return 0;
//        }
//
//        //记录当前深度
//        int depth = 0;
//
//        //借助队列进行层序遍历
//        Queue<TreeNode> queue = new LinkedList<>();
//
//        //首先将根节点入队
//        queue.offer(root);
//
//        //迭代获取深度
//        while (!queue.isEmpty()) {
//            //到达新的一层,深度+1
//            ++depth;
//
//            //获取当前层节点数量
//            int size = queue.size();
//
//            //将当前层节点出队
//            for (int i = 0; i < size; i++) {
//                TreeNode node = queue.poll();
//                if (node == null) {
//                    break;
//                }
//
//                //依次将节点的左、右子节点入队
//                if (node.left != null) {
//                    queue.offer(node.left);
//                }
//                if (node.right != null) {
//                    queue.offer(node.right);
//                }
//            }
//        }
//
//        //返回深度
//        return depth;
//    }
}
